package com.myc.subjects.sort;

import com.myc.subjects.utils.ArrayUtils;

import java.util.Arrays;

/**
 * LeetCode题号：75
 *
 * 颜色分类
 *
 * 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
 * 此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
 *
 * 示例 1：
 * 输入：nums = [2,0,2,1,1,0]
 * 输出：[0,0,1,1,2,2]
 *
 * 示例 2：
 * 输入：nums = [2,0,1]
 * 输出：[0,1,2]
 *
 * 示例 3：
 * 输入：nums = [0]
 * 输出：[0]
 *
 * 示例 4：
 * 输入：nums = [1]
 * 输出：[1]
 *
 * 提示：
 * n == nums.length
 * 1 <= n <= 300
 * nums[i] 为 0、1 或 2
 *
 * 进阶：
 * 你可以不使用代码库中的排序函数来解决这道题吗？
 * 你能想出一个仅使用常数空间的一趟扫描算法吗？
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/sort-colors
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Yansefenlei {

    public static void main(String[] args) {
        Yansefenlei y = new Yansefenlei();
        int[] nums = new int[]{2,0,2,1,1,0};
        y.sortColors3(nums);
        ArrayUtils.showArray(Arrays.stream(nums).boxed().toArray());
    }

    /**
     * 方法一：基于选择排序
     * 时间复杂度：O(n)
     * 定义当前指针从0开始
     * 基于选择排序，先选出0，与当前指针交换，当前指针右移，再选出1。
     */
    public void sortColors1(int[] nums) {
        //定义当前指针从0开始
        int curr = 0;
        //先将0交换到数组头部
        for(int i = 0; i < nums.length; i++){
            if(nums[i] == 0) swap(nums, curr++, i);
        }
        //再将1跟在0额后面
        for(int i = 0; i < nums.length; i++){
            if(nums[i] == 1) swap(nums, curr++, i);
        }
    }

    /**
     * 方法二：基于计数排序
     * 时间复杂度：O(n)
     * 遍历数组记录 0，1，2 三个数出现的次数，然后填回数组中
     */
    public void sortColors2(int[] nums){
        //定义三个变量，存储 0,1,2 出现的次数
        int count0 = 0, count1 = 0, count2 = 0;

        //统计次数
        for(int num : nums){
            switch(num){
                case 0:
                    count0++;
                    break;
                case 1:
                    count1++;
                    break;
                case 2:
                    count2++;
                    break;
                default:
                    break;
            }
        }

        //将统计结果一次放入数组中，这个方法很巧妙
        for(int i = 0; i < nums.length; i++){
            if(i < count0) nums[i] = 0;
            else if(i < count0 + count1) nums[i] = 1;
            else nums[i] = 2;
        }
    }

    /**
     * 方法三：基于快速排序
     * 时间复杂度：O(n)
     * 选取 1 做为基准元素，遍历数组，遇到0时将元素换到数组头部，遇到2时将元素换到数组尾部
     */
    public void sortColors3(int[] nums){
        int curr = 0;//定义遍历的当前指针
        int left = 0, right = nums.length - 1;//定义左右指针

        //边界条件是curr与right相遇，需要包括相遇点，因为相遇点没有判断过
        while(curr <= right){
            while(curr <= right && nums[curr] == 2) swap(nums, curr, right--);//遇到2时交换到数组尾部
            if(nums[curr] == 0) swap(nums, curr, left++);//遇到0时，放到最左边，这里不需要循环交换，因为只可能换回1
            curr++;
        }
    }

    //交换数组中两个元素的方法
    public void swap(int[] nums, int index1, int index2){
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }

    //官方题解
    //方法一：单指针
    public void sortColorsOfficial1(int[] nums) {
        int n = nums.length;
        int ptr = 0;
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 0) {
                int temp = nums[i];
                nums[i] = nums[ptr];
                nums[ptr] = temp;
                ++ptr;
            }
        }
        for (int i = ptr; i < n; ++i) {
            if (nums[i] == 1) {
                int temp = nums[i];
                nums[i] = nums[ptr];
                nums[ptr] = temp;
                ++ptr;
            }
        }
    }

    //方法二：双指针
    public void sortColorsOfficial2(int[] nums) {
        int n = nums.length;
        int p0 = 0, p1 = 0;
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 1) {
                int temp = nums[i];
                nums[i] = nums[p1];
                nums[p1] = temp;
                ++p1;
            } else if (nums[i] == 0) {
                int temp = nums[i];
                nums[i] = nums[p0];
                nums[p0] = temp;
                if (p0 < p1) {
                    temp = nums[i];
                    nums[i] = nums[p1];
                    nums[p1] = temp;
                }
                ++p0;
                ++p1;
            }
        }
    }

    //方法三：双指针
    public void sortColorsOfficial3(int[] nums) {
        int n = nums.length;
        int p0 = 0, p2 = n - 1;
        for (int i = 0; i <= p2; ++i) {
            while (i <= p2 && nums[i] == 2) {
                int temp = nums[i];
                nums[i] = nums[p2];
                nums[p2] = temp;
                --p2;
            }
            if (nums[i] == 0) {
                int temp = nums[i];
                nums[i] = nums[p0];
                nums[p0] = temp;
                ++p0;
            }
        }
    }
}

/**
 * 总结：对于排序问题，不能去调api，需要手写排序算法，需要掌握简单的排序算法如选择排序，计数排序，快速排序，堆排序等。同时还要能灵活掌握其变化来解决特定的实际问题
 */
